-- 2022-8-9

---[[ 14.4 队列及双端队列

    -- 在Lua语言中实现队列(queue)的一种简单方法是使用table标准库中的函数insert和remove
    -- 正如我们在5.6节中看到的 这两个函数可以在一个数组的任意位置插入或删除元素 
    -- 同时根据所做的操作移动其他元素 不过这种移动对于较大的结构来说开销很大

    -- 一种更高效的实现是使用两个索引 一个指向第一个元素 另一个指向最后一个元素
    -- 使用这种实现方式 我们就可以像示例14.2中所展示的那样以O(1)时间复杂度同时在首尾两端插入或删除元素了

    -- 一个双端队列
    -- 此时队列中存在 数据 first和last      first和last即承担键值对又承担队列的索引
    do
        function listNew()
            return {first = 0,last = -1}
        end
        function pushFirst(list,value)
            local first = list.first - 1
            list.first = first
            list[first] = value
        end
        function pushLast(list,value)
            local last = list.last + 1
            list.last = last
            list[last] = value
        end
        function popFirst(list)
            local first = list.first
            if first>list.last then
                error("list is empty")
            end
            local value = list[first]
            list[first] = nil
            list.first = first + 1
            return value
        end
        function popLast(list)
            local last = list.last
            if list.first>last then
                error("list is empty")
            end
            local value = list[last]
            list[last] = nil -- 使得元素能够被垃圾回收
            list.last = last - 1
            return value
        end
    end
    -- 如果希望严格的遵循队列的规划使用这个结构 那么就只能调用pushLast和popFirst函数 first和last都会不停的增长
    -- 不过由于我们在Lua语言中使用表来表示数组 所以我们既可以在1-20的范围内对数组进行索引 也可以在16777201-16777220的范围内索引数组
    -- 对于一个64位整型数而言 以每秒1000万次的速度进行插入也需要运行3万年才会发生溢出的问题
--]]